package HighMethod01;

public class test04 {

    //中间出现无需数据呢？？？怎么处理


    //非递归
    public int select(int val, int[] arr) {
        if (arr == null)
            return -1;
        int left = 0, right = arr.length - 1;
        int pos = -1;

        while (left <= right) {      //while(left < right)  left = right位置的数据还要比对
            int mid = (right - left) / 2 + left; //int mid = (left + right) / 2; 防止两个很大的数相加后超出整型范围
            if (val < arr[mid]) {
                right = mid - 1;
            } else if (val > arr[mid]) {
                left = mid + 1;
            } else {
                //如果找最左边的
//                while(mid > left && arr[mid -1] == val ) --mid;

                //如果找最右边的
//                while(mid > right&& arr[mid +1] == val ) ++mid;

                pos = mid;
                break;
            }
        }
        return pos;
    }

    //递归
    public int select2(int val, int[] arr, int left, int right) {
        if (arr == null)
            return -1;

        int pos = -1;
        if (left <= right) {
            int mid = (right - left) / 2 + left;    //int mid = ((right - left) >> 2) + left    位移运算效率更高

            if (val < arr[mid]) {
                right = mid - 1;
                pos = select2(val, arr, left, right);
            } else if (val > arr[mid]) {
                left = mid + 1;
                pos = select2(val, arr, left, right);
            } else {
                //最右查找
                while (mid > right && arr[mid + 1] == val) ++mid;

                return mid;
            }
        }
        return pos;
    }

}
